
//2866.美丽塔II
class Solution {
    typedef long long LL;
public:
    long long maximumSumOfHeights(vector<int>& nums) {
        int n=nums.size();
        vector<LL> right(n+1);  //统计右边从i位置向右的高度和
        vector<LL> left(n+1);     //统计从i位置向左数据和
        stack<pair<LL,LL>> st;   //使用pair来存储下标位置以及元素大小,存储下标方便对数据进行修改
        
        st.push({0,n});  //先放入一个元素,将n作为一个哨兵位,再使用i-x的时候更方便
        LL sum=0;
        for(LL i=n-1;i>=0;i--)  //统计右边和
        {
            while(!st.empty()&&st.top().first>nums[i])
            {
                auto [x,y]=st.top();
                st.pop();
                sum-=x*(st.top().second-y);
            }
            sum+=(st.top().second-i)*nums[i];
            st.push({nums[i],i});

            right[i]=sum;
        }

        while(!st.empty()) st.pop();  //统计左边和
        st.push({0,-1});
        sum=0;
        for(LL i=0;i<n;i++)
        {
            while(!st.empty()&&st.top().first>nums[i])
            {
                auto [x,y]=st.top();
                st.pop();
                sum-=x*(y-st.top().second);
            }
            sum+=(i-st.top().second)*nums[i];
            st.push({nums[i],i});

            left[i]=sum;
        }

        LL ret=0;
        for(LL i=0;i<n;i++)  //求最大值
            ret=max(ret,left[i]+right[i]-nums[i]);
        return ret;
    }
};